import java.util.ArrayList;
import java.util.List;

public class Solution51 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        int[] x = new int[n];
        queens(res, x, 0);
        return res;
    }

    private void queens(List<List<String>> res, int[] x, int k) {
        int n = x.length;
        if (k == n) {
            List<String> list = new ArrayList<>();
            for (int j : x) {
                //list.add(".".repeat(j) + "Q" + ".".repeat(n - j - 1));
                StringBuilder s = new StringBuilder(".".repeat(n));
                s.setCharAt(j, 'Q');
                list.add(s.toString());
            }
            res.add(list);
            return;
        }

        for (int i = 0; i < n; i++) {
            x[k] = i;
            if (!isValid(x, k)) {
                queens(res, x, k + 1);
            }
        }
    }

    private boolean isValid(int[] x, int k) {
        for (int i = 0; i < k; i++) {
            if (x[i] == x[k] || Math.abs(x[i] - x[k]) == Math.abs(i - k)) {
                return true;
            }
        }

        return false;
    }
}
